package com.zzh.shuffle;

import com.zzh.mymath.MyMath;


public class Shuffle {
    public static void main(String[] args) {
        String str = "1234abcd";
        char[] card = str.toCharArray();
        int from = 1;
        int to = card.length - 2;
        perfectShuffle(card, from, to, (to - from + 1) / 2);
        System.out.println(String.valueOf(card));
    }

    public static void perfectShuffle(char[] a, int from, int to, int n) {
        if (from >= to) {
            return;//如果递归到最后则直接返回
        } else if (from == to - 1) {
            MyMath.swap(a, from, to);//只剩2个数，直接交换并返回
            return;
        }
        int k = 0;//用来记录3^k中的k
        int m;//算法中的m
        int n2 = 2 * n;//算法中的2n
        int p = (n2 + 1);//p=3^k  3^k-1<2n<3^(k+1)-1->3^k<2n+1=p
        int k_3 = 1;//用于记录3^k的
        while (k <= p / 3) {//通过不断除以3找到最大k值，使得p>3^k成立
            k++;
            p /= 3;
            k_3 *= 3;
        }
        m = (k_3 - 1) / 2;//2m=3^k-1->m=(3^k-1)/2 至此得到了最大2m=3^k-1<2n，当然还有其他更好的办法

        rightCircle(a, from + m, from + n + m - 1, m);//循环右移的时候需要注意加上偏移量即可
        for (int i = 0, t = 1; i < k; ++i, t *= 3) {
            /*
            * 运用之前推导的环开始计算，因为算法中数组下标是从1开始的，我们这里的下标是从0开始
            * 所以在传偏移量的时候要减去1，这样偏移量加上算法计算出的值正好相互抵消符合实际下标
            *
            * */
            circle(a, from - 1, t, m * 2 + 1);
        }
        /*
        * 递归计算剩下的值
        * 起始下标为2m+偏移量，终止下标即为数组尾部，长度则是终止-起始+1再除以2因为我们需要的是n不是2n
        * */
        perfectShuffle(a, 2 * m + from, to, (to - (2 * m + from )+1) / 2);
    }

    //数组下标从1开始，主要是因为环是1->2->4->8->7->5->1
    public static void circle(char[] a, int from, int i, int n2) {
        for (int k = 2 * i % n2; k != i; k = 2 * k % n2) {
            char temp = a[i + from];
            a[i + from] = a[k + from];
            a[k + from] = temp;
        }
    }


    /*
     * 对于数组a，从下标from到to循环右移n个单位
     * */
    public static void rightCircle(char[] a, int from, int to, int n) {
        int m = n % (to - from + 1);
        reverse(a, to - m + 1, to);
        reverse(a, from, to - m);
        reverse(a, from, to);
    }


    public static void reverse(char[] a, int from, int to) {
        while (from < to) {
            MyMath.swap(a, from++, to--);
        }
    }
}
